package review;

import java.util.HashMap;
import java.util.Map;

/**
 * 手写LRU算法
 */
public class LRU缓存 {

    // 分别指向双向链表的头和尾节点
    private Node head;
    private Node tail;
    // 存储缓存key，和Node节点
    private Map<String,Node> map = new HashMap<>();
    private int capacity;

    public LRU缓存(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public void removeNode(Node node) {
        if(head == node) {
            head = head.next;
            head.pre.next = null;
            head.pre = null;
        } else if (node == tail){
            tail = tail.pre;
            tail.next.pre = null;
            tail.next = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
    }

    public void addToHead(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    public void addNodeToTail(Node node) {
        node.pre = tail.pre;
        tail.pre.next = node;
        node.next = tail;
        tail.pre = node;
    }

    public void moveNodeToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    public String get(String key) {
        Node node = map.get(key);
        if (node != null) {
            moveNodeToHead(node);
            return node.value;
        } else {
            return null;
        }
    }

    public void put(String key,String value) {
        Node node1 = map.get(key);
        if(node1 == null) {
            if(map.size() >= capacity) {
                removeNode(tail);
                map.remove(tail.key);
            }
            Node add = new Node(key,value);
            map.put(key,add);
            addToHead(add);
        } else {
            node1.value = value;
            moveNodeToHead(node1);
        }
    }

    class Node{
        String key;
        String value;
        Node pre;
        Node next;

        public Node() {
        }

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public Node(String key, String value, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    }
}
